1. Field of the Invention
The present invention relates to a square root extraction algorithm and a square root extraction circuit used for three-dimensional graphics processing which requires numerical calculations, particularly vector normalization.
2. Description of the Background Art
Graphics processing employing vector normalization, principally light source calculations, uses the result of vector normalization (XISQRT(X) where X is a vector and SQRT(X) is the square root of X) for processing. Thus, the increase in operation speed of the normalization is significant to increase the light source calculating speed. Attempts have been made to implement a square root extraction operation via software or special-purpose hardware. The software for the square root extraction operation requires no special hardware structure and hence necessitates no consideration for a circuit size (costs) when the LSI technique is applied thereto, but requires a large number of repetitive operations using an approximation algorithm. For this reason, the special-purpose hardware is used when a higher priority is given to a processing speed.
However, a conventional square root extraction circuit employing the square root extraction algorithm which determines conventional non-recovery type square roots has a hardware structure as disclosed in "Computer High-speed Operation System," Kindai Kagaku Sha Co., Ltd. Thus, to determine an N-digit square root, the conventional square root extraction circuit is subject to the following restrictions:
(1) N.multidot.(N+1)/2 adders are required. PA1 (2) CAS cells (controllable add/subtract cells) must be used which have a more complicated internal structure as one-unit adders than do full adders. PA1 (3) The operation of a digit of a given significance is not permitted to start until a carry output from the highest-order adder for the digit of the next higher significance (an extracted square root output for that digit) is determined. This decreases the operation speed.
The drawback (2) is described in detail hereinafter.
The CAS cell is a 4-input 4--output controllable add/subtract cell which receives data inputs A, B, a carry input CI, and a control input P to provide an addition (subtraction) output S and a carry output CO which satisfy the conditions described below, a data output B (equal to the data input B), and a control output P (equal to the control input P). EQU S=A (B P) CI EQU CO=(A+C).multidot.(B P)+A.multidot.C
The symbol " " means an exclusive-OR operation. The control input (output) P indicates an addition when it is "0", and indicates a subtraction when it is "1". In this manner, the CAS cell is a circuit which functions to perform a 1-bit addition/subtraction.
To determine the binary square root Q={0.q1 q2 q3 q4}.sub.2 of a binary number A={0.a1 a2 a3 a4 a5 a6 a7 a8}.sub.2, the conventional square root extraction algorithm determines whether the calculation for a digit of a given significance q(i+1) employs an addition or a subtraction, depending upon whether the value of the output digit of the next higher significance q(i) is "1" or "0". Thus, the conventional square root extraction circuit constructed such that the value of the square root extraction output digit of a given significance q(i) selectively determines the operation contents (addition or subtraction) in the CAS cells for the digit of the next lower significance q(i+1) is slow in operation speed and requires the CAS cells having the 1-bit addition/subtraction function.
FIG. 22 is a diagram of a square root extraction circuit employing the conventional algorithm.
As illustrated, two CAS cells are used for the output q1, four CAS cells for the output q2, six CAS cells for the output q3, and eight CAS cells for the output q4. In FIG. 22, an input shown as given to the middle of the top side of the block of each CAS cell corresponds to the data input A, an input shown as given obliquely to the upper-left corner of the block corresponds to the data input B, an input shown as given across the block corresponds to the control input P, an input shown as given to the right side of the block corresponds to the carry input CI, an output shown as provided from the left side of the block corresponds to the carry output CO, and an output shown as provided from the middle of the bottom side of the block corresponds to the addition (subtraction) output S. The CAS cell has a greater circuit size than that of a full adder and a half adder which are simple in construction, resulting in a complicated circuit structure of the conventional square root extraction circuit.